/**
 * 
 */
package dp;

/**
 * @author Michael
 * You are climbing a stair case. It takes n steps to reach to the top.
 * Each time you can either climb 1 or 2 steps. 
 * In how many distinct ways can you climb to the top?
 */
public class ClimbingStairs {

	// stairs number: 0, 1, 2, 3, 4, 5
	//        ways  : 0, 1, 2, 3, 5, 8
	//static int sum = 0;
	public static int stairsRecursive(int n, int index) {
		assert (n >= 0);
		int sum = 0;
		if (n == 0 || n < index) {
			return sum;
		}
		else if (n == index) {
			return sum + 1;
		}
		
		sum = sum + stairsRecursive(n, index + 1);
		sum = sum + stairsRecursive(n, index + 2);
		return sum;
	}
	
	
	// the nth step can from n-1 climb 1 step or n-2 climb 2 steps 
	// so f(n)=f(n-1)+f(n-2)
	public static long stairs(int n) {
		assert (n >= 0);
		if (n <= 2)
			return n;
		
		int minusOne = 2, minusTwo = 1, stair = 2;
		for (int i = 3; i <= n; ++i) {
			stair = minusOne + minusTwo;
			minusTwo = minusOne;
			minusOne = stair;
		}
		
		return stair;
	}

	// if 1, 2, 3 steps each time are allowed
	public static long stairsWithThree(int n) {
		assert (n >= 0);
		if (n <= 2)
			return n;
		if (n == 3)
			return 4;
		int minusOne = 4, minusTwo = 2, minusThree = 1;
		int stair = 0;
		for (int i = 4; i <= n; ++i) {
			stair = minusOne + minusTwo + minusThree;
			minusThree = minusTwo;
			minusTwo = minusOne;
			minusOne = stair;
		}
			
		return stair;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		for (int i = 0; i <= 30; i++)
//			System.out.println(stairs(i));
		
		for (int i = 0; i <= 30; i++) {
			System.out.println(stairsRecursive(i, 0));
		}
	}

	/**
	 * 
	 */
	public ClimbingStairs() {
		// TODO Auto-generated constructor stub
	}
}
